﻿#ifndef __DIJKSTRA__
#define __DIJKSTRA__
//************************** Dijkstra ***************************
//比Bellman-Ford 运行更快，但要求所有边的权值非负.
#define MAX_NODE_NUM 100
#define MAX_ARC_NUM 200
#include <iostream>
#include <limits>
#include <list>

struct graph{
	bool matrix[MAX_NODE_NUM][MAX_NODE_NUM];
	int node_num;
	int arc_num;
};

struct arc{
	char x;
	char y;
	int weight;
};

char nodes [MAX_NODE_NUM];
int father [MAX_NODE_NUM];
int distance [MAX_NODE_NUM];
graph g;
arc a[MAX_ARC_NUM];

int LocateNode(char c){
	int index = -1;
	for(int i = 0; i < g.node_num; ++i){
		if(nodes[i] == c){
			index = i;
			break;
		}
	}
	return index;
}

void CreateGraph(){
	for(int i = 0; i< g.node_num ;++i)
		for(int j = 0; j < g.node_num; ++j)
			g.matrix[i][j] = false;
	std::cout << "input node num :" ;
	std::cin >> g.node_num;
	for(int i = 0; i < g.node_num; ++i){
		std::cout << "input node [" << i+1 << "]'s lable:" ;
		std::cin >> nodes[i];
	}
	std::cout << std::endl << "input arc num :";
	std::cin >> g.arc_num;
	for(int i = 0; i < g.arc_num ; ++i){
		std::cout << "input arc and its weight:";
		std::cin >> a[i].x >> a[i].y >> a[i].weight ;
		int x = LocateNode(a[i].x),
			y = LocateNode(a[i].y);
		g.matrix[x][y] = true;
	}
}

void InitializeSingleSource(char c){
	for(int i =0; i < g.node_num; ++i){
		distance[i] = std::numeric_limits<int>::max();
		father[i] = i;
	}
	int index = LocateNode(c);
	distance[index] = 0;
}

void Relax(int x, int y){
	int w = FindWeight(x, y);
	if(w + distance[x] < distance[y]){
		distance[y] = w + distance[x];
		father[y] = x;
	} 
}

typedef std::pair<int*,int> dip;
struct cmp{
	inline bool operator()(const dip& a,const dip& b) const{
		return *a.first < *b.first;
	}
};

int FindWeight(int x, int y){
	int weight = std::numeric_limits<int>::max();
	for(int i = 0; i < g.arc_num; ++i)
		if(a[i].x == nodes[x] && a[i].y == nodes[y]){
			weight = a[i].weight;
			break;
		}
	return weight;	
}

void ShowPath(char destination){
	int d_index = LocateNode(destination);
	std::list<char> path;
	for(;;){	
		path.push_front(nodes[d_index]);
		if( d_index == father[d_index]) break;
		d_index = father[d_index];
	}

	std::list<char>::iterator it = path.begin();
	for(;;){
		if(it == path.end()) break;
		std::cout << *it++ << " -> ";
	}
	std::cout <<"end" << std::endl;
}
//反复选择具有最短估计值的顶点，并对该点的所有出边进行松弛
void Dijkstra(char s, char d){
	InitializeSingleSource(s);
	std::list<dip> que;
	for(int i = 0; i < g.node_num; ++i)
		que.push_back(std::make_pair(&distance[i],i));
	for(;;){
		if(que.empty()) break;
		que.sort(cmp());//可以不用排序，只要取得distance(最短估计值)最小即可
		dip top = que.front();
		for(int i = 0; i < g.node_num; ++i){
			if(g.matrix[top.second][i]){
				Relax(top.second, i);
			}
		}
		que.pop_front();
	}
	ShowPath(d);
}
#endif